use std::cmp::Ordering;
/// 二叉堆类型枚举
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BinaryHeapType {
    /// 最小堆（父节点值始终小于子节点）
    Min,
    /// 最大堆（父节点值始终大于子节点）
    Max,
}

/// 堆元素比较函数类型（使用Ordering替代C风格整型返回值）
///
/// # 泛型参数
/// - `T`: 堆中存储的元素类型
///
/// # 参数
/// - `v1`: 待比较的第一个元素引用
/// - `v2`: 待比较的第二个元素引用
pub type CompareFunc<T> = fn(v1: &T, v2: &T) -> std::cmp::Ordering;

/// 二叉堆核心数据结构实现
///
/// # 泛型参数
/// - `T`: 堆中存储的元素类型
#[derive(Debug)]
pub struct BinaryHeap<T> {
    /// 堆类型配置（最小堆/最大堆）
    heap_type: BinaryHeapType,
    /// 使用 Vec 存储堆元素，自动管理内存
    values: Vec<T>,
    /// 元素比较策略函数
    compare_func: CompareFunc<T>,
}

impl<T> BinaryHeap<T> {
    /// 创建新的二叉堆实例
    ///
    /// # 参数
    /// - `heap_type`: 指定堆类型（最小堆/最大堆）
    /// - `compare_func`: 自定义元素比较函数
    ///
    /// # 返回值
    /// 返回初始化完成的 [`BinaryHeap`] 实例
    pub fn new(heap_type: BinaryHeapType, compare_func: CompareFunc<T>) -> Self {
        Self {
            heap_type,
            values: Vec::with_capacity(16),  // 初始容量与C版本保持一致
            compare_func,
        }
    }
}


impl<T> BinaryHeap<T> {
    /// 获取堆中当前存储的元素数量
    ///
    /// # 返回
    /// 堆中元素的数量
    pub fn num_entries(&self) -> usize {
        self.values.len()
    }

    /// 内部比较方法（根据堆类型适配比较结果）
    ///
    /// # 参数
    /// - `v1`: 第一个待比较元素的引用
    /// - `v2`: 第二个待比较元素的引用
    ///
    /// # 返回
    /// 经过堆类型适配后的排序关系
    fn cmp(&self, v1: &T, v2: &T) -> std::cmp::Ordering {
        let ordering = (self.compare_func)(v1, v2);
        match self.heap_type {
            BinaryHeapType::Min => ordering,
            BinaryHeapType::Max => ordering.reverse(),
        }
    }
}


impl<T> BinaryHeap<T> {
    /// 移除并返回堆顶元素（最小/最大值）
    ///
    /// # 返回
    /// - `Some(T)`: 堆不为空时返回堆顶元素
    /// - `None`: 堆为空时返回 None
    pub fn pop(&mut self) -> Option<T> {
        if self.values.is_empty() {
            return None;
        }

        // 保存堆顶元素用于返回
        let result = self.values.swap_remove(0);

        if !self.values.is_empty() {
            let mut index = 0;
            let len = self.values.len();

            loop {
                let child1 = index * 2 + 1;
                let child2 = child1 + 1;

                let next_index = if child1 < len {
                    let cmp_child1 = self.cmp(&self.values[index], &self.values[child1]);
                    
                    if child2 < len {
                        let cmp_child2 = self.cmp(&self.values[index], &self.values[child2]);
                        let cmp_children = self.cmp(&self.values[child1], &self.values[child2]);

                        if cmp_child1 == Ordering::Greater && cmp_child2 == Ordering::Greater {
                            if cmp_children == Ordering::Greater {
                                child2
                            } else {
                                child1
                            }
                        } else if cmp_child1 == Ordering::Greater {
                            child1
                        } else if cmp_child2 == Ordering::Greater {
                            child2
                        } else {
                            break;
                        }
                    } else if cmp_child1 == Ordering::Greater {
                        child1
                    } else {
                        break;
                    }
                } else {
                    break;
                };

                self.values.swap(index, next_index);
                index = next_index;
            }
        }

        Some(result)
    }
}

impl<T> BinaryHeap<T> {
    /// 向堆中插入一个新元素
    ///
    /// # 参数
    /// - `value`: 要插入的元素
    ///
    /// # 返回值
    /// 总是返回 `true`（Rust 版本中省略内存分配失败检查）
    pub fn insert(&mut self, value: T) -> bool {
        self.values.push(value);
        let mut current_index = self.values.len() - 1;

        while current_index > 0 {
            let parent_index = (current_index - 1) / 2;
            match self.cmp(&self.values[parent_index], &self.values[current_index]) {
                std::cmp::Ordering::Less => break,
                _ => {
                    self.values.swap(parent_index, current_index);
                    current_index = parent_index;
                }
            }
        }

        true
    }
}